package Mysinglelist;

public class MySinglelist implements MyList {
    public ListNode head;
    public ListNode last;

    //内部类创建链表
    static class ListNode{
        public int val;                 //节点值
        public ListNode next;           //节点的next域
        public ListNode prev;           //节点的next域

        //对节点初始化
        public ListNode(int val)
        {
            this.val = val;
        }
    }
    //打印链表
    @Override
    public void display() {
            ListNode cur = head;
            while (cur!=null)
            {
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
        System.out.println();
    }
    //头插法
    @Override
    public void addfirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;

    }

    @Override
    public void addmid(int data,int index) {
        ListNode node = new ListNode(data);
        int mid = size()/2;
        int length = size();
        if( index >= length || index <= 0)                //下标判定
        {
            System.out.println("下标越界！");
            return;
        }
        if(size()==0)                                   //若链表为空
        {
            head = node;
            last = head;
        }
        else {
            if( index >= mid )                    //若下标在链表的前半段
            {
                ListNode fast = head.next;
                ListNode slow = head;
                while( index-1 > 0 )
                {
                    fast = fast.next;
                    slow = slow.next;
                    fast.prev = slow.next;
                    index--;
                }
                slow.next = node;
                node.next = fast;

            }
            else if ( index == length || mid == 0)                   //若下标刚好与目前的链表长度相等或者下标是1
            {
                last.next = node;
                last = last.next;
            }
            else                                                     //若下标在链表的后半段
            {
                ListNode fast = last.prev;
                ListNode slow = last;
                int num = length-index;
               while( num >0)
                {
                    fast = fast.prev;
                    slow.prev = fast.next;
                    num--;
                }
                fast.next = node;
                node.next = slow.prev;
            }
        }
    }

    //尾插法
    @Override
    public void addlast(int data) {
        ListNode node = new ListNode(data);
        if(head == null)                    //先判断链表是否为空，如果为空那就将插入的节点作为头结点
        {
            head = node;
            last = node;
        }
        else {
            last.next = node;
            last  = last.next;
        }
    }
    //返回链表长度
    @Override
    public int size() {
        ListNode cur = head;
        int size = 0;
        while(cur!=null)
        {
            cur = cur.next;
            size++;
        }
        return size;
    }


    //删除指定节点元素
    @Override
    public void remove(int index) {
        int length = size();
        if(index >= length || index < 0 )
        {
            System.out.println("下标越界！");
        }
        else {
            if(index==0)                    //删除的是头结点
            {
                ListNode cur = head.next;
                head = head.next;
            }
            else{
                if(length == 2)   //删除的是尾节点且链表长度为2
                {
                    head.next = null;
                    last = head;
                }
                else {
                    ListNode cur = head.next;
                    ListNode slow = head;
                    ListNode fast = cur.next;
                    int len =1;
                    while (index-len!= 0) {
                            fast = fast.next;
                            slow = slow.next;
                            cur = cur.next;
                            len++;
                    }
                    slow.next = fast;
                }
            }
        }
    }
    //改变指定节点元素
    @Override
    public void replace(int data, int index) {
        ListNode node = new ListNode(data);
        int length = size();
        if(index>=length || index<0){
            System.out.println("下标越界！");
        }
        else {
            ListNode cur = head.next;
            ListNode slow = head;
            ListNode fast = cur.next;
            int len =1;
            while (index-len!= 0) {
                fast = fast.next;
                slow = slow.next;
                cur = cur.next;
                len++;
            }
            slow.next = node;
            node.next = fast;
        }

    }

    //查找链表是否存在对应的节点元素
    @Override
    public boolean search(int key) {
        ListNode cur = head;
        while(cur!=null)
        {
              if(cur.val==key)
              {
                  return true;
              }
              cur = cur.next;
        }
        return false;
    }
    //查找index位置所在的结点
    @Override
    public void find(int index) {
       int length = size();
       if(index>=length || index<0)
       {
           System.out.println("下标越界！");
       }
       else {
           ListNode cur = head;
            while(index !=0)
            {
                cur = cur.next;
                index--;
            }
           System.out.println("index位置节点的值是： "+cur.val);
       }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(12);      // 0
        ListNode node2 = new ListNode(34);      // 1
        ListNode node3 = new ListNode(45);      // 2
        ListNode node4 = new ListNode(56);      // 3
        ListNode node5 = new ListNode(67);      // 4

        ListNode node6 = new ListNode(23);

        MySinglelist list = new MySinglelist();
        list.addlast(node1.val);
        list.addlast(node2.val);
        list.addlast(node3.val);
        list.addlast(node4.val);
        list.addlast(node5.val);

        System.out.println(list.search(67));   // 查
        list.find(2);

     /*   list.remove(3);                          //删
        list.display();*/

        /*list.replace(node6.val,3);               //改
        list.display();*/

        /*  list.addmid(node6.val,2);              //中间插入节点
        list.display();*/
    }
}
